class Solution
{
public:
    int countPaths(int n, vector<vector<int>> &roads)
    {
        vector<vector<pair<int, int>>> graph(n);
        for (auto &road : roads)
        {
            graph[road[0]].push_back({road[1], road[2]});
            graph[road[1]].push_back({road[0], road[2]});
        }

        vector<long long> dist(n, LONG_LONG_MAX);
        vector<long long> ways(n);
        dist[0] = 0;
        ways[0] = 1;

        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;

        pq.push({0, 0});
        while (!pq.empty())
        {
            auto [d, u] = pq.top();
            pq.pop();
            if (d > dist[u])
            {
                continue;
            }

            for (auto &[v, l] : graph[u])
            {
                long long newDist = l + dist[u];
                if (newDist < dist[v])
                {
                    dist[v] = newDist;
                    ways[v] = ways[u];
                    pq.push({newDist, v});
                }
                else if (newDist == dist[v])
                {
                    ways[v] = (ways[u] + ways[v]) % 1'0000'0000'7;
                }
            }
        }
        return ways[n - 1];
    }
};